package LeetCode._02算法基础.day02二分查找;

import org.junit.Test;
import 题组.Solution;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 12 - 9:52
 * @Description 峰值元素是指其值严格大于左右相邻值的元素。
 * 给你一个整数数组nums，找到峰值元素并返回其索引。
 * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 * @Version 中等
 */
public class _162寻找峰值 {
    static int[] nums = {1,2,3,1};
    @Test
    public void solve(){
        int res = findPeakElement1(nums);
        System.out.println(res);
    }
    /*by me 暴力法*/
    public int findPeakElement(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            if(i == 0 ){
                if(i + 1 < nums.length &&nums[i] > nums[i + 1])
                    return i;
            }else if(i == nums.length - 1){
                if(i - 1 >= 0 && nums[i] > nums[i - 1])
                    return i;
            }else if(i + 1 < nums.length && i - 1 >= 0 &&nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){
                return i;
            }
        }
        return 0;
    }

    //3.爬坡法
    public int findPeakElement3(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < nums[mid+1]) {  //上坡
                l = mid + 1;    //舍弃左边（右边一定有峰：最右边或中间凸起）
            } else {    //右边是下坡，
                r = mid;    //舍弃右边（左边一定有峰：最左边或中间凸起）
            }
        }
        return l;
    }
    /*官方思路*/
    //1.寻找最大值，其一定是峰值
    public int findPeakElement1(int[] nums) {
        int idx = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[idx]) {
                idx = i;
            }
        }
        return idx;
    }
    //2.类二分查找
    public int findPeakElement2(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
                ans = mid;
                break;
            }
            if (compare(nums, mid, mid + 1) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
    // 方便处理 nums[-1] 以及 nums[n] 的边界情况
    public int[] get(int[] nums, int idx) {
        if (idx == -1 || idx == nums.length) {
            return new int[]{0, 0};
        }
        return new int[]{1, nums[idx]};
    }

    public int compare(int[] nums, int idx1, int idx2) {
        int[] num1 = get(nums, idx1);
        int[] num2 = get(nums, idx2);
        if (num1[0] != num2[0]) {
            return num1[0] > num2[0] ? 1 : -1;
        }
        if (num1[1] == num2[1]) {
            return 0;
        }
        return num1[1] > num2[1] ? 1 : -1;
    }
    
}
